package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.x.XClassic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 17. 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 */
@XClassic
public class LC17_LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Utils.printInJson(new Solution1().letterCombinations("23"));
    }

    /**
     *
     */
    @KBackTracking
    static
    class Solution {
        private final Map<Character, String> keyboard = new HashMap<Character, String>(){{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        public List<String> letterCombinations(String digits) {
            List<String> cmb = new ArrayList<>();
            int n = digits.length();
            if(n == 0) return cmb;

            char[] digitsArr = digits.toCharArray();
            char[] path = new char[n];
            dfs(0, digitsArr, path, cmb);
            return cmb;
        }

        private void dfs(int i, char[] digitsArr, char[] path, List<String> cmd) {
            if (i == digitsArr.length) {
                cmd.add(new String(path));
                return;
            }

            for(char ch : keyboard.get(digitsArr[i]).toCharArray()) {
                path[i] = ch;
                dfs(i + 1, digitsArr, path, cmd);
            }
        }
    }


    /**
     *
     */
    static
    class Solution1 {
        private final String[] keyboard = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        public List<String> letterCombinations(String digits) {
            List<String> answer = new ArrayList<>();
            int n = digits.length();
            if (n == 0) {
                return answer;
            }

            char[] digitsArr = digits.toCharArray();
            char[] path = new char[n];
            dfs(0, digitsArr, path, answer);

            return answer;
        }

        private void dfs(int i, char[] digitsChars, char[] path, List<String> answer) {
            if (i == digitsChars.length) {
                answer.add(new String(path));
                return;
            }

            for (char ch : keyboard[Integer.parseInt(digitsChars[i] + "")].toCharArray()) {
                path[i] = ch;
                dfs(i + 1, digitsChars, path, answer);
            }
        }
    }
}
